计蒜客【NOIP2017模拟2】银河战舰 <线段树+矩阵>

Problem

【NOIP2017模拟2】银河战舰

Description

瑞奥和玛德利德是非常好的朋友。瑞奥平时的爱好是吹牛，玛德利德的爱好是戳穿瑞奥吹的牛。
这天瑞奥和玛德利德来到了宇宙空间站，瑞奥向玛德利德炫耀这个空间站里所有的银河战舰都是自己的。整个空间站可以看成一个无限大的二维平面，每个战舰都可以看做一个点，在空间站中一共分布着 艘银河战舰。
玛德利德：“你说这些都是你的，那你让他们动一动啊”。
瑞奥：“诶你看,那艘动了！”。
玛德利德：“操作指令由我来发，一共有 种动的方法……”。
瑞奥：“我觉得这样有失公正……”。

Input

第一行一个正整数 ，表示战舰的数量。
接下来 行，每行两个实数，代表第 个战舰的 坐标。
然后一个正整数 ，代表调度的次数。
接下来 行操作，每个操作都是如下类型的一种：

• ：把编号在 区间内的战舰 坐标加上 ， 坐标加上 。
• ：把编号在 区间内的战舰沿 轴翻转。
• ：把编号在 区间内的战舰沿 轴翻转。
• ：把编号在 区间内的战舰沿直线 翻转。
• ：把编号在 区间内的战舰绕原点逆时针旋转 。

Output

输出包括 行，代表着 艘战舰经过 次调度之后的坐标（保留两位小数）。

Sample Input

3
1 2
-2 2.5
0 -3
3
X 1 3
M 1 3 3 6
R 1 3 90

Sample Output

-4.00 4.00
-3.50 1.00
-9.00 3.00

Constraint

特殊性质 1：对于所有调度，保证 ,。
特殊性质 2：不存在形如 的操作。
特殊性质 3：不存在形如 的操作。
对于所有测试数据，保证输入的 坐标以及 都最多保留两位小数，，任何时刻任何战舰的横纵坐标绝对值都不会超过 。

Source

2017 NOIP 提高组模拟赛（二）Day2

标签：线段树 矩阵

Solution

用线段树维护二维平面坐标变换。

对于点，对其维护一个矩阵：

（下面的是留给常数的）
那么对于五种变换，都对应着这个矩阵乘一个转移矩阵。
例如对于变换，其对应的转移矩阵为

若有，则对应

类似地，另外四种变换分别对应四个转移矩阵：

显然区间修改相当于区间乘一个矩阵，可以用线段树维护。

时间复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define PI acos(-1.0)
#define mid ((s+t)>>1)
using namespace std;
typedef double dnt;
int n, m; dnt x[MAX_N+5], y[MAX_N+5];
struct Matrix {
    dnt ele[3][3];
    Matrix () {memset(ele, 0, sizeof ele);}
    inline Matrix operator * (const Matrix &x) const {
        Matrix ret;
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++) ret.ele[i][j] += ele[i][k]*x.ele[k][j];
        return ret;
    }
    inline bool operator == (const Matrix &x) const {
        for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++)
            if (ele[i][j] != x.ele[i][j]) return false;
        return true;
    }
} e, M, X, Y, O, R, tr[MAX_N<<2];
void build(int v, int s, int t) {
    if (s == t) {
        tr[v].ele[0][0] = x[s];
        tr[v].ele[1][0] = y[s];
        tr[v].ele[2][0] = 1;
        return;
    }
    tr[v] = e;
    build(v<<1, s, mid);
    build(v<<1|1, mid+1, t);
}
void downtag(int v) {
    if (tr[v] == e) return;
    tr[v<<1] = tr[v]*tr[v<<1];
    tr[v<<1|1] = tr[v]*tr[v<<1|1];
    tr[v] = e;
}
void modify(int v, int s, int t, int l, int r, Matrix x) {
    if (s >= l && t <= r)
        {tr[v] = x*tr[v]; return;}
    downtag(v);
    if (l <= mid) modify(v<<1, s, mid, l, r, x);
    if (r >= mid+1) modify(v<<1|1, mid+1, t, l, r, x);
}
void print(int v, int s, int t) {
    if (s == t) {
        printf("%.2lf ", tr[v].ele[0][0]);
        printf("%.2lf\n", tr[v].ele[1][0]);
        return;
    }
    downtag(v);
    print(v<<1, s, mid);
    print(v<<1|1, mid+1, t);
}
int main() {
    scanf("%d", &n), R.ele[2][2] = 1;
    e.ele[0][0] = e.ele[1][1] = e.ele[2][2] = 1;
    M.ele[0][0] = M.ele[1][1] = M.ele[2][2] = 1;
    O.ele[0][1] = O.ele[1][0] = O.ele[2][2] = 1;
    X.ele[0][0] = X.ele[2][2] = 1, X.ele[1][1] = -1;
    Y.ele[0][0] = -1, Y.ele[1][1] = Y.ele[2][2] = 1;
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", x+i, y+i);
    build(1, 1, n), scanf("%d", &m);
    while (m--) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'M') {
            int l, r; dnt p, q;
            scanf("%d%d%lf%lf", &l, &r, &p, &q);
            M.ele[0][2] = p, M.ele[1][2] = q;
            modify(1, 1, n, l, r, M);
        }
        if (opt[0] == 'X') {
            int l, r; scanf("%d%d", &l, &r);
            modify(1, 1, n, l, r, X);
        }
        if (opt[0] == 'Y') {
            int l, r; scanf("%d%d", &l, &r);
            modify(1, 1, n, l, r, Y);
        }
        if (opt[0] == 'O') {
            int l, r; scanf("%d%d", &l, &r);
            modify(1, 1, n, l, r, O);
        }
        if (opt[0] == 'R') {
            int l, r; dnt a;
            scanf("%d%d%lf", &l, &r, &a);
            R.ele[0][0] = cos(a*PI/180.0);
            R.ele[0][1] = -sin(a*PI/180.0);
            R.ele[1][0] = sin(a*PI/180.0);
            R.ele[1][1] = cos(a*PI/180.0);
            modify(1, 1, n, l, r, R);
        }
    }
    return print(1, 1, n), 0;
}